The invention also relates to a method of creating a position-coding pattern, use of a position-coding pattern, a device for position determination and storage media storing computer programs for generating and for decoding of the position-coding pattern.
In many situations it is desirable to be able to determine an absolute position on a surface, for example in connection with the digitization of drawings or when one wishes to create an electronic version of handwritten information.
U.S. Pat. No. 5,852,434 describes a device for the determination of an absolute position. The device comprises a writing surface provided with a position code by means of which it is possible to determine X- and Y-coordinates, a detector capable of detecting the position code, and a processor capable of determining the position of the detector in relation to the writing surface on the basis of the detected position code.
Three examples of a position code are provided in U.S. Pat. No. 5,852,434. The first example is dots, each of which is made up of three concentric circles. The outermost circle represents the X-coordinate and the middle circle represents the Y-coordinate. Furthermore, the two outermost circles are divided into 16 parts, which depending upon whether they are filled in or not indicate different numbers. This means that each pair of coordinates X, Y is coded with a dot with a specific appearance.
In the second example, the coordinates are indicated in each point on the writing surface with the aid of a barcode, a barcode for the X-coordinate being placed above a barcode for the Y-coordinate.
As a third example, it is stated that a checkerboard pattern can be used for coding the X- and Y-coordinates. However, no explanation is given of how the checkerboard pattern is structured or how it can be translated into coordinates.
One problem associated with the known pattern is that it is made up of complex symbols. The smaller these symbols are the more difficult it is to produce the patterned writing surface and the greater the risk of incorrect position determination. But the larger the symbols, the poorer the position resolution.
A further problem is that the image processing becomes fairly complicated because of the fact that the symbols that must be interpreted are complex.
Yet another problem is that the sensor surface of the device used for recording the symbols must be made large enough to enable it to record four symbols at the same time so that it will definitely record at least one symbol in its entirety, which is necessary in order to carry out the position determination.
WO 92/17859 discloses a device for position determination which comprises a code surface with a pattern which has a so-called windowing pattern. This means that the pattern has the property that for each arbitrary partial surface of the pattern of a predetermined magnitude, the location of the partial surface in the pattern can be determined. The pattern is composed of so-called m-sequences which have the property that each subsequence of the length k appears only once in the sequence.
Appendix A of WO 92/17859 provides the following examples of how the pattern can be composed and how a position can be decoded.
Start from the following m-sequences: s=(0,0,1,0,1,1,1) and t=(0,1,1). Build a position-coding pattern by letting a first column in the pattern equal the sequence s. To build the following columns, look at the t-sequence. If the first element in the t-sequence is 0, the second column consists of the s-sequence. If the first element instead is 1, the second column consists of the s-sequence circularly shifted by one step. The following columns are built in a corresponding manner according to the values of the elements in the t-sequence. The following pattern is then obtained:
Now assume that one wants to find the position of a partial surface with the below indicated subset of the pattern.
The first column in the subset is (1,0,1). This sub-sequence appears in position 2 in the s-sequence. The circular shifts in the subset are (1,1). This subsequence appears in position 1 in the t-sequence. The accumulated appears in the pattern are (0,0,1,2) and therefore the vertical position of the subset is 2+0=2. The position of the subset on the partial surface thus is (1,2).
With this pattern, the above described problems are obviated, involving complex symbols and the need for recording four symbols in order to definitely record one symbol in its entirety.
An interesting characteristic of a position-coding pattern of this type, however, is the possibility of coding a large pattern with many unique positions so that position determination can be carried out on a surface which is as large as possible. In the example above, the magnitude is limited in the vertical direction by the length of the s-sequence and the magnitude in the horizontal direction by the length of the t-sequence. The length of these sequences can, however, not be increased infinitely since the sequences should have the characteristic that if one takes a subsequence of k-bits, this subsequence should only appear in one position in the sequence. An increase of the sequence length may thus require an increase of the subsequence length and thus an increase of the partial surface that must be recorded to be able to determine a position.
It is an object of the present invention to completely or partly obviate this problem.
This object is achieved by a product according to claim 1, a method of creating a position-coding pattern according to claim 10, electronic storage media according to claims 14, 15 and 16, a device for position determination according to claim 20 and use of a position-coding pattern according to claim 23.
More specifically, the invention relates to a product for position determination, which product has a surface and a position-coding pattern which extends across the surface and codes a plurality of positions on the surface, each position of a said plurality of positions being coded by a specific part of the position-coding pattern and each such specific part of the position-coding pattern also contributing to the coding of adjacent positions, said position-coding pattern further being based on a first string of symbols which contains a first predetermined number of symbols and which has the characteristic that if one takes a second predetermined number of symbols from the first string of symbols, the location of these symbols in the first string of symbols is unambiguously determined, the first string of symbols being used to determine the position in a first dimension on the surface. Moreover the position-coding pattern contains at least a first row of symbols which are arranged according to the first string of symbols, and at least a second row of symbols which are arranged according to a second string of symbols having the same characteristic as the first string of symbols, a displacement being obtained between the first and the second string of symbols along the first and the second row when the first and the second string of symbols are repeated on them.
By using the displacement between a first and a second string of symbols, it is possible to code a larger number of positions in the direction in which the first and the second string of symbols are used for the coding. If the first string of symbols has the length n and the second string of symbols has the length nxe2x88x921, it is possible to code, instead of n-positions, n(nxe2x88x921) positions in the direction in which the first string of symbols is used by utilizing the first displacement or interference obtained between the first and the second in this direction.
It is evident that the position-coding pattern is of the same type, i.e. has the same characteristic as the windowing pattern described by way of introduction.
The term xe2x80x9crowxe2x80x9d should here be interpreted in a wide sense and not be considered limited to horizontal rows, but also comprise all rows independently of the angle at which they are arranged to the horizontal plane.
One example of strings of symbols having the above-described characteristics is the xe2x80x9cm-sequencesxe2x80x9d mentioned by way of introduction.
In a preferred embodiment, the second string of symbols is a subset of the first string of symbols. This has the advantage that the memory need for decoding of the pattern decreases.
The position-coding pattern can be formed with two rows only. In most applications, however, it is necessary to determine positions on a surface that has a larger extent in both dimensions. To this end, the position-coding pattern comprises in an advantageous embodiment a plurality of first rows and a plurality of second rows, the displacements being between the first and the second string of symbols being of different magnitude between different rows. The different displacements between the rows can be used to determine the position in the second dimension.
To enable efficient determination of the position in a second dimension on the surface, a position-coding pattern is advantageously arranged in such manner that the displacement between the first and the second string of symbols in each pair of an adjoining first and second row is within one of a plurality of predetermined ranges. The displacement between a pair of two adjoining rows will thus vary merely within a predetermined range along the pair of rows. Thus the range is constant along the pair of rows.
In an advantageous embodiment, the position-coding pattern can further be based on a third string of symbols having the same characteristic as the first string of symbols, the third string of symbols being used to determine the position in a second dimension on the surface.
Despite the increase in the number of codable positions in the first dimension, the coding in the second dimension can thus be carried out by means of a string of symbols of the above-mentioned type. This makes it possible to determine the position in the second dimension without capacity-requiring calculations. A simple table look-up is sufficient.
The third string of symbols can advantageously be a number series consisting of numbers which each are a function of said displacements. The numbers in the number series thus represent the size of the displacements.
The first and the second rows can advantageously begin in varying positions in the first and the second strings of symbols.
In the presently preferred embodiment, the first string of symbols is a series of binary numbers and the third string of symbols is a number series with a different base, so that great displacements are allowed between the first and second rows and, thus, many positions in the first dimension can be coded.
The product to which the position-coding pattern is applied can be any product having a surface upon which one wishes to determine a position. It can be of a passive type. Accordingly, it need not transmit signals itself; rather it has a pattern which can be read by means of an active device.
The position-coding pattern can be any arrangement of lines, figures, surfaces or the like which enables the coding of positions in the above manner.
The symbols in the pattern can be of any suitable type whatever. They are preferably graphical so that no character recognition (OCR) need be made in the position determination, but they could also consist of numbers or characters.
The pattern can be made up, for example, of a plurality of discrete symbols of at least a first type. The coding can be binary, in which case for example the presence of a symbol can represent a one and the absence of a symbol can represent a zero. However, this type of coding can cause problems in positions which are coded only or primarily with zeros.
In the most preferred embodiment, the symbols are therefore merely of a first and a second type which have the same form but different magnitude.
Such a pattern can also be used for binary coding. It is very easy to apply to a surface since the symbols can be very simple, for example consisting of two dots of different diameters. The product having a surface with this pattern is thus easy to manufacture since the information content of each symbol is small. Furthermore, it facilitates image processing.
The position-coding pattern can be implemented using any parameter which can be read by an area sensor on a partial surface on the surface across which the position-coding pattern extends. The parameter can be electrical or chemical or of some other type. The pattern can, for example, be designed in such a way that the conductance on the surface varies in the manner indicated. However, the pattern is preferably optically readable since this makes applying it to the surface easy. It should thus be capable of reflecting light. However, the light need not be in the visible range.
The positions can preferably be indicated as coordinates in a Cartesian or a polar coordinate system.
It has been found difficult to generate at random a position-coding pattern without ambiguities which has the characteristic that a position can be determined by means of an arbitrary partial surface of a predetermined size. This problem is solved according to another aspect of the invention by a method of creating a position-coding pattern, which position-coding pattern is designed for coding a plurality of positions on a surface, comprising the step of arranging, on at least a first row, symbols in accordance with a first string of symbols which contains a first predetermined number of symbols and has the characteristic that if one takes a second predetermined number of symbols from the first string of symbols, the location of these symbols in the string of symbols is unambiguously determined, and further comprising the step of arranging, on at least a second row, symbols in accordance with a second string of symbols having the same characteristic as the first string of symbols, a displacement being obtained between the first and the second string of symbols along the first and the second row when the first and the second string of symbols are repeated on them.
This method is advantageous because it enables rule-based generation of an unambiguous position-coding pattern which can code more positions in a first dimension that what can be coded merely with the first string of symbols.
That stated above regarding the position-coding pattern on the product is, of course, in applicable parts also related to the method.
The decoding of the above position-coding pattern is advantageously carried out by means of a computer program.
According to another aspect of the invention, it therefore relates to storage medium for a computer, on which there is stored a computer program with instructions for decoding of the position-coding pattern on a product according to any one of claims 1-9.
The generation of the position-coding pattern is also advantageously made by means of a computer program, which can control a printer or some other type of printing device. To this end, the invention relates according to one more aspect to a storage medium for a computer, on which there is stored a computer program with instructions for generation of the position-coding pattern on a product according to any one of claims 1-9.
According to one more aspect of the invention, it relates to a storage medium for a computer, on which there is stored a computer program for determining the position of a partial surface on a surface which is provided with a position-coding pattern comprising a plurality of symbols, on the basis of an input signal representing the partial surface, said computer program comprising instructions for identifying a plurality of symbols in the input signal, which are arranged in a predetermined number of symbol groups; determining the location of each symbol group in at least a first predetermined string of symbols; determining a difference number which is based on the relative positions of the symbol groups in said at least a first predetermined string of symbols; determining the location of said difference number in a second predetermined number series; determining a first coordinate for the position of the partial surface on the surface on the basis of the position of said difference number in the second predetermined number series, and determining a second coordinate for the position of the partial surface on the surface on the basis of the relative positions of two adjoining symbol groups in said at least a first predetermined string of symbols.
In the decoding of the position-coding pattern, a partial surface of the pattern is read. This partial surface contains a number of symbol groups which can be arranged in rows or in some other predetermined manner. In the determination of the one coordinate, use is made of not only one symbol group but two adjoining symbol groups, which permits determination of position in one dimension for the position-coding pattern of the above type.
The input signal advantageously is an image.
The storage medium can be any type of medium on which a computer program can be stored, such as a diskette, a disk, a memory in a computer or some other processor-based device.
The program for generating the pattern is preferably used in a computer which is connected to a printer or some other device which makes it possible to produce the pattern on the product.
The program for decoding the pattern can preferably be arranged in a handheld device which is used for reading the pattern or in a computer to which the reading device is connected.
According to still another aspect of the invention, it relates to a device for position determination, comprising a sensor for reproducing one partial surface of a plurality of partial surfaces on a surface and image-processing means which are adapted to decode a position-coding pattern on a product according to any one of claims 1-9.
Since the image-processing means of the device can determine the position in a xe2x80x9crule-basedxe2x80x9d manner on the basis of the above-described position-coding pattern, the device need not have a large amount of memory capacity, which is advantageous in respect of the production cost of the device and the possibility of making a stand alone unit.
The image-processing means advantageously consist of a suitably programmed processor.
The invention can be implemented as an independent unit, which advantageously can transfer position information in a wireless manner to an external unit. Alternatively, the sensor can be positioned in a first casing while the image-processing means are positioned in another casing, e.g. a personal computer to which images recorded by the sensor are transferred.
According to one more aspect of the invention, it relates to use of a position-coding pattern for determining a position, said position-coding pattern being based on a first string of symbols which contains a first predetermined number of symbols and which has the characteristic that if one takes a second predetermined number of symbols from the first string of symbols, the location of these symbols in the string of symbols is unambiguously determined, and said position-coding pattern consisting of the symbols in the first string of symbols, the symbols being placed in at least a first row in accordance with the first string of symbols and at least a second row in accordance with a second string of symbols having the same characteristic as the first string of symbols, a displacement being obtained between the first and the second string of symbols along the first and the second row when the first and the second string of symbols are repeated on them.
Use may consist of, for instance, storage of the pattern in electronic form.
The invention can be applied in a number of different fields. It can be used to continuously record the position of a pen which is passed across a sheet of paper or some other writing surface. It can also be used in all contexts where the position of a tool or the like need be determined. It may also be used as a mouse pad for a mouse.